package com.wlr.study.order;

/**
 * 插入排序
 * 构建有序序列
 * 对于未排序数据，在已排序序列中从后往前扫描，找到相应位置插入
 * <p>
 * 从第一个元素开始，该元素可以认为已经被排序；
 * 取出下一个元素，在已经排序的元素序列中从后向前扫描
 * 如果该元素大于新元素，将该元素移动到下一个位置
 * 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
 * 将新元素插入刀该位置后
 * 重复步骤2~5
 *
 * @author lrwang
 * @version 1.0
 * @date 2022/3/17 0:14
 */
public class InsertionSort {
    public static int[] insertionSort(int[] array) {
        if (array.length == 0) {
            return array;
        }
        int current;
        for (int i = 0; i < array.length-1; i++) {
            current = array[i + 1];
            int preIndex = i;
            while (preIndex >= 0 && current < array[preIndex]) {
                array[preIndex + 1] = array[preIndex];
                preIndex--;
            }
            array[preIndex + 1] = current;
        }
        return array;
    }
    public static void main(String[] args) {
        int[] nums = new int[]{5, 2, 6, 4, 8, 3, 1, 7};
        int[] ints = InsertionSort.insertionSort(nums);
        for (int a : ints) {
            System.out.println(a);
        }
    }
}
